"""
算法思想：通过相邻元素的比较和交换，使值较大的元素逐渐从前面移向后面（如同水中气泡上浮），每一趟排序将最大元素 "浮" 到数组末尾。

代码解释：
外层循环控制排序趟数，最多需要n-1趟（n为数组长度）。
引入swapped标记优化：若某趟排序未发生交换，说明数组已有序，可提前终止。
内层循环负责相邻元素比较，每趟排序后最大元素已到位，因此比较范围逐趟缩小（n-1-i）。
时间复杂度：最好情况（有序）为O(n)，最坏情况和平均情况为O(n²)。

"""
def bubble_sort(arr):
    # 获取数组长度
    n = len(arr)
    # 外层循环控制排序趟数，共需n-1趟;即比如有6个待排序的对象，则外层需要排序5趟
    for i in range(n - 1):
        # 标记本趟是否发生交换，优化无交换的情况
        swapped = False
        # 内层循环进行相邻元素比较，每趟减少一个比较对象
        for j in range(n - 1 - i):
            # 若前面元素大于后面元素，交换它们
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # 若本趟未发生交换，说明数组已有序，提前结束
        if not swapped:
            break
        print("过程中一次冒泡后的结果:",arr)
    return arr

# 测试
#arr = [4,2,5,8,1,0,6,3,9]
arr = [7,1,4,3,5,2]
sorted_arr = bubble_sort(arr)
print("冒泡排序最终结果:", sorted_arr)  # 输出:
